package org.lex.game.sudoku.model.solver;

import java.lang.reflect.Method;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicInteger;

import ms.sudoku.util.IntSet;

import org.lex.game.sudoku.datatype.Result;
import org.lex.game.sudoku.model.Point;
import org.lex.game.sudoku.model.SudokuModel;
import org.lex.game.sudoku.model.SudokuModelListener.Cause;
import org.lex.game.sudoku.util.Stack;
import org.lex.game.sudoku.util.SyncProxy;
import org.lex.game.sudoku.util.SyncProxy.SyncFilter;
import org.lex.game.sudoku.view.Operation;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import common.Sudokus;

public class DefaultSolver implements Solver {
	private boolean sync = true;
	private AtomicBoolean debug = new AtomicBoolean(true);
	private AtomicInteger delay = new AtomicInteger(0);

	private Logger log = LoggerFactory.getLogger(DefaultSolver.class);

	public void setDebug(boolean b) {
		this.debug.set(b);
	}

	public void setDelay(int newDelay) {
		this.delay.set(newDelay);
	}

	public Result solve(SudokuModel model, SolverObserver observer) throws InterruptedException {
		if (null == observer) {
			observer = new DefaultSolverObserver();
		}
		if (sync) {
			// model = new SyncSudokuModel(model);
			model = (SudokuModel) SyncProxy.newSwingSyncInstance(model, new SyncFilter() {
				@Override
				public boolean needSync(Object delegate, Method method, Object[] args) {
					Class<?> retType = method.getReturnType();
					if (true == log.isTraceEnabled()) {
						log.trace("returnType=" + retType + ", method=[" + method + "], args=" + Arrays.toString(args));
					}
					return void.class.equals(retType) || Void.class.equals(retType);
				}
			}, SudokuModel.class);
			// observer = new SyncSolverObserver(observer);
			observer = (SolverObserver) SyncProxy.newSwingSyncInstance(observer, new SyncFilter() {
				@Override
				public boolean needSync(Object delegate, Method method, Object[] args) {
					return true;
				}
			}, SolverObserver.class);
		}

		Decisions decisions = new Decisions();
		History history = new History();
		while (!this.shouldStop(model)) {
			// fill out all single-hint-cells
			Result fillResult = this.fillSingleHintCells(model, history, observer);
			// observer.singleHintCellFilled(fillResult.second());
			if (fillResult.isOK()) {
				/*
				 * no errors in filling single-hint-cells -> make decision or
				 * game solved
				 */
				if (!this.shouldStop(model)) {
					/*
					 * if game not completed & not more single-hint-cells-> make
					 * new decision
					 */
					decisions.buildDecision(model);

					Decision toUse = decisions.makeDecision();
					observer.beginDecision(toUse);
					history.add(this.fill(model, toUse.row, toUse.column, toUse.number, observer));
				} else {
					/*
					 * if game completed -> solved
					 */
					return Result.OK;
				}
			} else {
				/*
				 * error in filling single-hint-cells -> rollback or game can
				 * not be solved
				 */
				if (decisions.canRollback() && decisions.canMakeDecision()) {
					// Decision toUse = decisions.rollbackAndMakeDecision(model,
					// history, observer);
					decisions.rollback(model, history, observer);
					Decision toUse = decisions.makeDecision();
					observer.beginDecision(toUse);
					history.add(this.fill(model, toUse.row, toUse.column, toUse.number, observer));
				} else {
					// can not be solved
					return Result.ERROR;
				}
			}
		}
		return Result.OK;
	}

	private Result fillSingleHintCells(SudokuModel model, History history, SolverObserver observer)
			throws InterruptedException {
		int count = 0;
		int gridSize = model.getGridSize();
		boolean changed = false;
		do {
			changed = false;
			for (int row = 0; row < gridSize; row++) {
				for (int col = 0; col < gridSize; col++) {
					int num = model.get(row, col);
					if (Sudokus.isEmpty(num)) {
						IntSet hints = model.getHints(row, col);
						if (null == hints || hints.isEmpty()) {
							// can not be solved --> end
							return Result.ERROR;
						} else if (1 == hints.size()) {
							// single hint --> fill current cell with the hint
							history.add(this.fill(model, row, col, hints.pop(), observer));
							count++;
							changed = true;
						}
					}
				}
			}
		} while (true == changed && !this.shouldStop(model));
		log.info(count + " single-hint-cells filled");
		return Result.OK;
	}

	private boolean shouldStop(SudokuModel model) {
		return model.isCompleted() || (!model.checkAll(false).isValid()) || Thread.currentThread().isInterrupted();
	}

	private Operation fill(SudokuModel model, int row, int column, int num, SolverObserver observer)
			throws InterruptedException {
		int oldNum = model.get(row, column);
		model.set(Cause.USER, row, column, num);
		observer.fillCell(row, column, num);
		if (this.delay.get() > 0) {
			try {
				Thread.sleep(this.delay.get());
			} catch (RuntimeException e) {
				e.printStackTrace();
			}
		}
		return new Operation(System.currentTimeMillis(), new Point(row, column), oldNum, num);
	}

	private static final class History {
		private Deque<Operation> operations = new ArrayDeque<>();

		public void add(Operation o) {
			this.operations.addLast(o);
		}

		public int rollback(SudokuModel model, Decision decision) {
			int rollbackCount = 0;
			while (false == this.operations.isEmpty()) {
				Operation last = this.operations.removeLast();
				int row = last.getWhere().x;
				int col = last.getWhere().y;
				int num = last.getNewValue();
				model.set(Cause.SYSTEM, row, col, last.getOldValue());
				rollbackCount++;
				if (row == decision.row && col == decision.column && num == decision.number) {
					break;
				}
			}
			return rollbackCount;
		}
	}

	private static final class Decisions {
		private boolean debug = true;
		private Stack<Decision> pendingDecisionList = new Stack<>();
		private Stack<Decision> usingDecisionList = new Stack<>();

		private final Logger log = LoggerFactory.getLogger(Decisions.class);

		public void buildDecision(SudokuModel model) {
			Point bestCell = null;
			int gridSize = model.getGridSize();
			int minHintsCount = Integer.MAX_VALUE;
			IntSet bestHints = null;
			for (int row = 0; row < gridSize; row++) {
				for (int col = 0; col < gridSize; col++) {
					int num = model.get(row, col);
					if (Sudokus.isEmpty(num)) {
						IntSet hints = model.getHints(row, col);
						if (hints.size() < minHintsCount) {
							minHintsCount = hints.size();
							bestCell = new Point(row, col);
							bestHints = hints;
						}
					}
				}
			}
			if (null != bestHints) {
				log.info("making " + bestHints.size() + " decisions on " + bestCell.viewString());
				for (int hint : bestHints) {
					this.pendingDecisionList.push(new Decision(bestCell.x, bestCell.y, hint));
				}
				this.showDecisions("after buildDecision():");
			}
		}

		public boolean canMakeDecision() {
			return !this.pendingDecisionList.isEmpty();
		}

		public Decision makeDecision() {
			this.showDecisions("before makeDecision():");
			Decision toUse = this.pendingDecisionList.pop();
			this.usingDecisionList.push(toUse);
			this.showDecisions("after makeDecision():");
			return toUse;
		}

		public boolean canRollback() {
			return !this.usingDecisionList.isEmpty();
		}

		public void rollback(SudokuModel model, History history, SolverObserver observer) {
			this.showDecisions("before rollbackAndMakeDecision():");
			Decision rollbackTo = pendingDecisionList.peek();
			this.rollbackTo(model, history, rollbackTo, observer);
			this.showDecisions("after rollbackAndMakeDecision()");
		}

		private void rollbackTo(SudokuModel model, History history, Decision rollbackTo, SolverObserver observer) {
			Decision rollbackFrom = null;
			for (Decision peek : this.usingDecisionList) {
				if (peek.row == rollbackTo.row && peek.column == rollbackTo.column) {
					rollbackFrom = peek;
					break;
				}
			}
			if (null != rollbackFrom) {
				while (true) {
					Decision pop = this.usingDecisionList.pop();
					// rollback
					int rollbackCount = history.rollback(model, pop);
					observer.rollbackDecision(pop, rollbackCount);
					if (pop == rollbackFrom) {
						break;
					}
				}
			}
		}

		private void showDecisions(String title) {
			if (debug) {
				log.info(title);
				log.info("Pending Decisions: " + this.pendingDecisionList);
				log.info("InUsing Decisions: " + this.usingDecisionList);
			}
		}
	}

}
